int cmp(int* x, int* y)
{
    return *x - *y;
}
int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int sum = 0;
    if (nums[0] >= 0)
    {
        sum -= nums[0];
        for (int i = 1; i < numsSize; i++)
        {
            sum += nums[i];
        }
    }
    else if (nums[numsSize - 1] <= 0)
    {
        if (k <= numsSize)
        {
            for (int i = 0; i < k; i++)
            {
                sum -= nums[i];
            }
            for (int i = k; i < numsSize; i++)
            {
                sum += nums[i];
            }
        }
        else
        {
            for (int i = 0; i < numsSize - 1; i++)
            {
                sum -= nums[i];
            }

            if ((k - numsSize) % 2 == 0)
                sum -= nums[numsSize - 1];
            else
                sum += nums[numsSize - 1];
        }
    }
    else
    {
        int n = 0;
        for (int i = 0; i < numsSize; i++)
        {
            if (nums[i] < 0)
            {
                n++;
            }
            else
            {
                break;
            }
        }
        if (n >= k)
        {
            for (int i = 0; i < numsSize; i++)
            {
                if (i < k)
                {
                    sum -= nums[i];
                }
                else
                {
                    sum += nums[i];
                }
            }
        }
        else
        {
            if ((k - n) % 2 == 0)
            {
                for (int i = 0; i < numsSize; i++)
                {
                    if (i < n)
                        sum -= nums[i];
                    else
                        sum += nums[i];
                }
            }
            else
            {
                for (int i = 0; i < numsSize; i++)
                {
                    if (i < n - 1)
                    {
                        sum -= nums[i];
                    }
                    else if (i > n)
                    {
                        sum += nums[i];
                    }

                }
                if (nums[n - 1] + nums[n] > 0)
                {
                    sum = sum + nums[n - 1] + nums[n];
                }
                else if (nums[n - 1] + nums[n] < 0)
                {
                    sum = sum - nums[n - 1] - nums[n];
                }
                else
                {
                    sum = sum + nums[n] + nums[n - 1];
                }
            }
        }
    }
    return sum;
}